package com.cat.dynamicPlanning;

import java.util.Arrays;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/
 * @create 2025/9/5 23:42
 * @since JDK17
 */

public class Solution86 {
    int[][] dp;
    int[] nums;
    int dfs(int l, int r) {
        if (l > r) {
            return 0;
        }
        if (l == r) {
            return nums[r + 1] - nums[l - 1];
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        int ans = Integer.MAX_VALUE;
        for (int i = l; i <= r; i++) {
            ans = Math.min(ans, dfs(l, i - 1) + dfs(i + 1, r));
        }
        return dp[l][r] = ans + nums[r + 1] - nums[l - 1];
    }

    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        nums = new int[m + 2];
        dp = new int[m + 1][m + 1];
        Arrays.sort(cuts);
        for (int i = 0; i < m; i++) {
            nums[i + 1] = cuts[i];
        }
        nums[m + 1] = n;
        for (int i = 0; i < m + 1; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(1, m);
    }
}
